While the 21st century has seen great advances in technology, there has also been a rise in criminals using robots and incidents involving biomonsters, as well as other previously unheard-of disasters. To better deal with these threats, the police department decided to embark on the Brave Police project-building high tech robot detectives to counter these threats.
One day, a fourth grader called Yuuta Tomonaga stumbles upon the police's new project, a sentient police robot called Deckerd. Soon after he visits Deckerd several times and teaches him various things about life, Deckerd's AI becomes self-aware and he begins to develop a "heart". But the day comes when he is to be sent into action, and the police prepare to wipe his memory, which includes his friendship with Yuuta. Yuuta tries to stop the wipe but is unsuccessful.
A criminal piloting a large robot attacks the police parade transporting Deckerd in order to steal him. Deckerd is dormant inside a truck but hears Yuuta's voice and reactivates, saving the city and defeating the robot. The police decide to hire Yuuta as the boss of the new "Brave Police" division, an elite force of robot detectives, of which Deckerd is the first.
More robot detectives join the force as time passes, and they and Yuuta face off against a variety of foes.