Unfortunately, few houses have deeds now unless the land is unregistered. If so, yes that is the place to start - the Deeds will not necessarily tell you when the house was built but may help you pin it down. If not the land registry title can give some information which may help.
Is it a new property or an older one? If new (ie 20-30 years) the planning department will have such details. If much older, you may want to visit your record office.