Brady made his maiden speech in the House of Commons on 2 June 1997. In 1998 he made enquiries to John Bourn, at the time Comptroller and Auditor General, on his decision not to publish a National Audit Office report on the controversial Al-Yamamah arms deal. The same year, Brady was one of only 13 Conservative MPs who voted in favour of an equal age of consent. He became a Member of the Education and Employment Select committee, and Parliamentary Private Secretary (PPS) to the Chairman of the Conservative Party, Michael Ancram in 1999. He was made an Opposition Whip by William Hague in 2000. In February 2000, Brady complained about anti-grammar school literature circulated to parents in Altrincham by Michael Evans, then head of Trinity Church of England High School, arguing that this violated rules about public funds being used for campaign material – a complaint subsequently upheld by Secretary of State for Education David Blunkett. That same year Brady would become an Opposition Spokesman on Education and Employment.