A lot, as others have mentioned, depends on luck, location and whether your family descend from high social class's. For example, Welsh ancestry is quite well known for keeping good genealogical records earlier that the 13th century as many bards wrote poems and obituaries of prominent families and their naming system of using 'ap/ab' for 'son of' and 'ferch/verch' for 'daughter of' also helps as you can have an entire line traced back 100's of years in a single paragraph.
Whilst yes there are also always the gateway ancestors, however even these require careful study as many of the pedigrees available for them (including visitations) are incorrect or have large gaps and therefore need to be carefully matched with sources available for the respective periods.
There are also other ways that a person can trace further back from the 1500's but that depends on whether those sources have been released yet. For example land records held by the aristocracy in their archives that have yet to be made public.
Records that can be helpful other than parish records are: wills, manorial documents, assize rolls, state papers, indictments, pipe rolls, Inquisition post mortem, coroners inquests, etc. All of these sometimes have detailed family entries from parents, siblings, children, spouses, etc.
The other problem many face is locating the records or even reading them. For example
www.medievalgenealogy.org.uk has some good help guides and transcribed materials. If you are looking for older records sometimes you have to look at university archives such as
http://aalt.law.uh.edu/ which offers original images of rolls from 1199 to the reign of Victoria. All in latin however.
That all said, despite what others say elsewhere, the chances of you actually being able to prove your farmer ancestors were somehow descended from a gateway ancestor (nobility or royalty) with concrete evidence (i.e. wills, land records or the above records) is very slim unless they were the eldest child of eldest child or had siblings mentioned in the afore mentioned documents.