Het eerste verhaal van Natasja, luchtstewardess verscheen bijna bij toeval in het weekblad Robbedoes. François Walthéry, haar geestelijke vader had sinds 1967 enkele tekeningen gemaakt van deze nieuwe vrouwelijke heldin op verzoek van toemalige redacteur van Robbedoes die talent zag in de manier waarop hij vrouwelijke stripfiguren kon tekenen.

Charles Dupuis, die toen nog toezag op de selectie van de tekeningen, was gewonnen voor het idee, maar de toemalige eindredacteur deed de tekeningen in de diepste kelders van de uitgeverij belanden. De Franse censuur van die periode betreffende vrouwelijke figuren was enorm. Meer dan een half jaar later, na een redactionele verandering, vond de nieuwe hoofdredacteur Thierry Martens de tekeningen terug. Hij drong aan bij Walthéry om snel het verhaal af te werken.

Natasja's eerste verhaal verscheen voor het eerst in Robedoes nr. 1663 van 26 februari 1970, waar ze al dadelijk de cover van mocht sieren. Er zouden nog vele avonturen volgen.

Terwijl Walthéry nog voor Peyo werkte aan De Smurfen en aan Steven Sterk begon hij samen met Roland Goosssens (Gos) te werken aan de eerste twee verhalen van Natasja. Na deze twee scripts zou Gos het meerendeel van zijn tijd gaan besteden aan andere series en kon niet meer verder werken met Walthéry. Van dan af aan zou de tekenaar aan verschillende scenaristen vragen om verhalen te ontwikkelen voor Natasja. Men beweert zelfs dat Walthéry niet begint aan een nieuw verhaal als hij niet kan terugvallen op drie verschillende scenarios.

Na Gos zou Walthéry gaan samenwerken met ondermeer Etienne Borgers, Maurice Tillieux, Marc Wasterlain en Peyo als scenaristen. Dit is dan ook de reden waarom er zoveel variatie zit in de verhalen van Natasja. Gaande van de eerste twee klassieke avonturen over het thriller achtige "Metalen Geheugen" naar de Science-fiction verhalen als daar zijn "De raadselachtige gedaanten" en "Luchtspiegelingen".