Mahou Sensou, Hitsugi no Chaika Recommendations
Both protagonist happens to bump into a girl, and without knowing much about them decided to help them. They soon travel and help protect the girl without much decision.
Both anime involves fighting and magical weapons/power, both girls use guns while the male protagonist uses a sword. If you enjoy magical fighting than you'll like these both.
Hitsugi no Chaika contains several elements found in Mahou Sensou - a magical war that took place prior to the start of the series, a girl with a gun that fires magic, a protagonist caught in a slightly odd love triangle, and multiple warring factions. However, Hitsugi no Chaika pulls them off far, far better than Mahou Sensou did and is a far better series overall.
Both involves, magical girl with guns who happens to bump into guy and his friend where their live where never the same again. the difference, the girl in one anime carries a pistol, while the girl in the other anime carries a big gun.