Deze lijn ontstond op 18 september 1997, toen de route van de oude [[Lijn 71 Amsterdam, Centraal Station - Station Sloterdijk|lijn 71]] ingrijpend werd gewijzigd. Lijn 71 bleef station Sloterdijk en het Amstelstation via Nieuw West en Oud Zuid met elkaar verbinden, maar verloor het traject tussen het Centraal Station en het Amstelstation. Toegevoegd werd het traject van het Centraal Station naar station Sloterdijk. Tegelijkertijd werd van maandag- t/m donderdagnacht de frequentie teruggebracht van een halfuursdienst naar een uursdienst.
Op [[Dienstregeling GVB 2004|14 december 2003 ]] werd een nieuw nachtnet ingevoerd met de lijnen 351 t/m 363. Lijn 71 werd op deze datum opgeheven, het nieuwe net kende geen vergelijkbare lijn die met een tangentiële route Nieuw West en Oud Zuid met elkaar verbond.