I have realized that a part of my project can be separated from the main code base and maintained as a completely separate program. I would like that the new project (repo) will keep all the history etc from before splitting. What is the best way of achieving this
You should be able to use the bzr split command.
See bzr split --help for more info.