Sachverhalt: A. X._ erstattete am 26. August 2010 Strafanzeige gegen seine von ihm getrennt lebende Ehefrau Y._ wegen falscher Anschuldigung im Sinne von Art. 303 StGB. Gleichzeitig machte er Zivilforderungen geltend. Mit Entscheid vom 18. Oktober 2010 stellte das damals für die Untersuchung zuständige Amtsstatthalteramt Luzern das Strafverfahren gegen Y._ ein und trat auf die Zivilforderungen von X._ nicht ein. Der Staatsanwalt visierte den Einstellungsentscheid am 26. Oktober 2010. Gegen den Einstellungsentscheid reichte X._ am 15. November 2010 Rekurs ein. Er beantragte die Überweisung der Strafsache an das zuständige Gericht und ersuchte zudem um Gewährung unentgeltlicher Rechtspflege. Mit Entscheid vom 25. März 2011 trat das Obergericht des Kantons Luzern auf den Rekurs nicht ein. Zur Begründung führte es an, weder habe sich X._ als Privatkläger im Sinne von § 35 Abs. 1 des Gesetzes des Kantons Luzern vom 3. Juni 1957 über die Strafprozessordnung (SRL 305; im Folgenden: StPO/LU) konstituiert, noch komme ihm Opferstellung nach dem Opferhilfegesetz (SR 312.5) zu. Das Gesuch um unentgeltliche Rechtspflege wies das Obergericht wegen Aussichtslosigkeit ab. B. Mit Beschwerde in Strafsachen an das Bundesgericht vom 18. Mai 2011 beantragt X._ im Wesentlichen die Aufhebung des Entscheids des Obergerichts. Das Obergericht beantragt in seiner Vernehmlassung die Abweisung der Beschwerde. Die Oberstaatsanwaltschaft und die Beschwerdegegnerin haben auf eine Stellungnahme verzichtet. 