Fossilization doesn't happen suddenly; it is a gradual process. While it is happening, the organism is a sub-fossil. It is temping to suggest that a non-fossil organism is totally organic and a fossil organism is totally mineral. But that's difficult to apply universally in practice, since many organisms are partly mineral while they are alive. For instance, bones and teeth, the calcareous spines of echinoids, the shells of 'shells', the siliceous spicules of sponges. However, fossilization is a process primarily of mineralization, and in can be recognized by the presence of minerals where in the living organism there were none (excluding things like gall stones!)
The rate of mineralization depends on many things, which can be generalized as 'the preservational environment'. That includes aspects like presence of water and/or other fluids, pressure, temperature, entombing material (for instance sediment), scavenging, physical erosion - and how they vary over time. Many combinations of those factors can result in an organism disappearing - being eaten, dissolving, (re)crystallizing, wearing away, etc. But if conditions and events are favourable, an organism can eventually become fossilized, though soft tissues are less likely to be preserved than hard tissues such as bones. To generalize, that may take from tens of thousands of years to millions of years.
Strictly speaking, marks left by living organisms and preserved in rock are also fossils - trace fossils. These may form in only a few years or decades - however long it may take for a sediment to become lithified (years-decades is an extreme case; usually it takes millions of years for sediment to become stone). ...Or lava or volcanic ash to solidify... The casts of the bodies of the unfortunate people killed in the eruption at Pompei and Herculaenum in 79AD are in fact trace fossils, and they formed in only a few hours (probably).