První podlahová krytina velmi podobná linoleu vznikla v roce 1844. Tehdy získal patent na její výrobu Angličan E. Galloway. Tato podlahová krytina se vyráběla z rozmělněného korku spojeného gutaperčou, což je vysokomolekulární uhlík podobný kaučuku (získávaný z mlékovitého výronu tropických stromů).

Linoleum v pravém slova smyslu si nechal patentovat o 19 let později (1863) jiný Angličan, Frederick Walton. Traduje se , že na myšlenku ho přivedlo tvrdnutí lněného oleje při malování olejových obrazů na plátně. Walton použil tentýž princip pro “své” linoleum: ke lněnému oleji a pigmentům, které tvoří základ olejových barev, přidal – jako jeho předchůdce – korkovou drť a pryskyřici. Navíc tam však přimíchal dřevěnou moučku a mletý vápenec a zejména spojil tuto vrstvu s hrubým jutovým tkanivem, které tvořilo podklad lina. Samotný název pak odvodil Walton z latinských výrazů pro len (linum) a olej (oleum).

Vznikla tak podlahová krytina vynikajících užitných vlastností: byla “teplá”, odolávala vodě a vysoké teplotě (odhozená zápalka, cigareta), měla nevtíravý a neprošlapatelný vzorek a přitom všem životnost 30-40 let.

Walton však pokračoval. V roce 1877, 14 let po svém patentování linolea, užil ten samý princip na pokrývání stěn. Jen místo jutového tkaniva použil papír. Tak vznikla tzv. lincrusta. Byla velmi dekorativní, pracovalo se s ní jako s tapetou, vyžadovala však zvláštní péči, protože byla poměrně těžká a silná.

Význam a i úspěch linolea byl nesporný. Není proto divu, že se postupně objevili výrobci, kteří se snažili nabídnout podobné výrobky. Rozšířily se zejména dva druhy. Jednak to bylo tzv. asfaltové lino. Ve své podstatě to byla asfaltová papírová lepenka a barevným potiskem na lícové straně. Měla jedinou výhodu: byla levná. Jinak se skutečným linoleem nemohla v ničem soupeřit. Velice vážným konkurentem byla umělohmotná (vinylová) lina. Ta se objevila v roce 1947. Byla levnější a nabízela větší rozsah barev a vzorů. Stala se módou, která způsobila zastavení výroby klasického linolea v 70. letech minulého století. Když horečka opadla a získaly se dlouhodobější zkušenosti, mnozí zákazníci zjistili, že výrobci ve svých reklamách na skvělé vlastnosti lina “opoměli” upozornit např. na to, že vinylová lina se poměrně brzy prošlapou (vzorek bývá natištěný), většinou neodolávají vyšší teplotě (zápalka, cigareta) a jsou neprůlinčitá, tzn., že podlaha nevětrá (vlhkost). A tak se v 90. letech opět obnovila výroba původního linolea z přírodního materiálu.