The majority of properties in the UK are now registered at the Land Registry and won't have any deeds. A sale of part of existing land will need to be registered separately.
Land Registry Form AP1 is filed by the purchaser's solicitors and registers the name of the new proprietor (thereby 'changing the deeds'). Fees vary from �150 upwards depending on sale price.
Certain unregistered overriding interests must be disclosed and will bind even registered land such as easements or covenants.