Deze nieuwe [[nachtbus]] werd geïntroduceerd op [[Dienstregeling concessie Amstelland-Meerlanden 2010|13 december 2009]] na het opheffen van de vorige [[Lijn N72 Amsterdam Centraal Station - Schiphol Plaza / NS|Niteliner 72]]. De nieuwe N71 nam het traject tussen Amsterdam en Aalsmeer over en ging verder rijden naar Kudelstaart. Vanaf [[Dienstregeling concessie Amstelland-Meerlanden 2011|12 december 2010]] verviel de halte Hobbemastraat en op [[Dienstregeling concessie Amstelland-Meerlanden 2012|11 december 2011]] werd de frequentie verlaagd naar 1x/uur.
Op [[Dienstregeling concessie Amstelland-Meerlanden 2016|13 december 2015]] werd het nacht bezuiden Amsterdam vereenvoudigd. Elke nachtlijn kreeg een lijnnummer dat verwijst naar de reguliere streeklijn op hetzelfde traject. Dit lijnnummer werd daarom, met ongewijzigde route en dienstregeling, vernummerd naar [[Lijn N72 Amsterdam Centraal Station - Kudelstaart Bilderdammerweg|N72]].