Yes, one can do so. As soon as one is going to work and not get social support from the state, he/she can live wherever he/she wants within Germany.
Just in case you would like to move between cities some time later:
After you register at new address, within several weeks your documents will be transferred to the immigration office of the new city.
Before registering at new address you can still apply for anything at the immigration office of your place of residence. From my personal experience, there should be no strict rules, you can just communicate with old/new immigration office on the personal level.
The only thing to consider is that during the transfer of documents it might be harder to apply for anything, so do it either before registering at the new address at the old office or one month after at the new office.