La Fille de nulle part est né dans l'esprit de Jean-Claude Brisseau par désir de retourner à des conditions de tournage proche de celles de ses débuts, mais aussi à un cinéma disparu : "J’avais la nostalgie des films de la Nouvelle Vague, comme Tirez sur le pianiste (1960), par exemple, où pendant les cinq premières minutes, on ne voit pas grand-chose à l’image, mais c’est le film de Truffaut qui m’a le plus touché", explique-t-il.
20 ans après son Lion d'Or au Festival de Berlin pour le film Celine, le réalisateur Jean-Claude Brisseau a remporté un prix important dans un autre festival célèbre : celui de Locarno, où La Fille de nulle part a été récompensé d'un Léopard d'Or, par le jury du réalisateur thaïlandais Apichatpong Weerasethakul.
Jean-Claude Brisseau n'était pas destiné à jouer le premier rôle masculin : il pensait le confier à son ami Claude Morel qui joue quand même dans le film. Le cinéaste s'est laissé convaincre par son entourage de faire l'acteur, une situation dans laquelle il ne s'était jamais retrouvé auparavant : "(...) ce travail a été très pénible car je devais apprendre tous les jours des textes par cœur, souvent très longs, et en même temps, jouer et faire la mise en scène."
Virginie Legeay, qui interprète le premier rôle féminin, connaît Jean-Claude Brisseau depuis plusieurs années : ils se sont d'abord rencontrés alors qu'elle était étudiante à l'école de cinéma la FEMIS, puis elle est devenue son assistante sur le tournage du film Les Anges exterminateurs en 2006. La Fille de nulle part est leur premier face à face à l'écran.
La Fille de nulle part a été tourné avec un petit budget, en caméra DV et dans l'appartement parisien de Jean-Claude Brisseau. Ce manque d'argent a obligé l'équipe à faire preuve d'inventions en tous genres : "Les travellings étaient réalisés avec une poussette sur laquelle on avait fixé une planche horizontale et sur laquelle on avait posé le pied de la caméra", se souvient le cinéaste.
Malgré son prix au Festival de Locarno, le film de Jean-Claude Brisseau n'était pas certain de connaître une date de sortie. Au départ, c'était la société de distribution Capricci Films qui devait s'occuper de la sortie du film mais un litige commercial opposant les distributeurs au cinéaste bloqua la situation. C'est finalement la jeune société Les Acacias qui a fini par distribuer La Fille de nulle part.