Друкуватися почала в 1961 році. Була членом Спілки письменників України, а з 1977 року - Спілки письменників СРСР. Пише в жанрі короткої прози, що відрізняється особливою поетичністю в описі навколишньої дійсності. Автор книжок українською мовою «Інтеграл Піфагора» (1967), «Сніжні ягоди» (1970), "Велика ріка" (1973), «Місяць активного сонця» (1979) , «Найкоротша ніч року» (1983), «Казка про синього птаха» (1986), «На єдиній дорозі» (1988), «Таємниця пентагіри» (1989), «Що записано в книгу життя» (1990), «Таємниця точки Хе-Гу» (1993, у співавт. з Миколою Колбун).
29 жовтня 2003 Наталія Околітенко була обрана на пост голови Національної Спілки письменників України. Це трапилося після того, як загальними зборами НСПУ голова цієї організації Володимиру Яворівському був винесений вотум недовіри і він був зміщений з посади. Цікаво, що за рік до цього В. Яворівським письменниця була виключена з НСПУ «за дії, які суперечать статуту організації». Це переобрання фактично розділило НСПУ на два протиборчі табори.
У 1990 році в київському видавництві «Молодь» вийшла її збірка фантастичних творів під назвою «Крок вікінга», куди увійшло півтора десятки оповідань і повістей. Ця книга об'єднала майже всі НФ твори, які Наталія Околітенко періодично публікувала з 1976 року.
