Heine taught herself to play tennis by hitting the ball against the wall of her father's butcher shop in Winterton. She received the nickname "Bobbie" as a junior player when, at a tournament, a representative of the South African Tennis Union remarked that the round shape of her face resembled that of an English policeman. In 1925, she won the Natal singles championship at the age of 15.
Heine made her first trip to Europe in 1927. In May, she won the Surrey Championships at Surbiton, defeating Irene Bowder Peacock; together they won the doubles title. She again teamed up with compatriot Bowder Peacock to win the doubles title at the 1927 French Championships, her first and only Grand Slam title, defeating the British partnership of Peggy Saunders and Phoebe Holcroft Watson in two straight sets. At the same tournament, she achieved her best Grand Slam singles performance by reaching the semifinals, which she lost in three sets to eventual winner Kea Bouman. At the 1927 Wimbledon Championships, she was defeated in the third round of the singles event in three sets by Phoebe Holcroft. In doubles, she and Bowder Peacock reached the final, but lost to the American couple Helen Wills and Elizabeth Ryan in straight sets.
In 1929, on her second European trip, Heine won the singles title at the Irish Open, defeating compatriot Billie Tapscott in three sets. In addition, she won the British Hard Court Championships, emerging victorious from a closely fought three-sets final against Joan Ridley that lasted two hours. At the 1929 French Championships, she was seeded second in the singles event and was beaten in the quarterfinal by Cilly Aussem in three sets. She and Alida Neave were runners-up in the doubles, losing the final to Kea Bouman and Lilí Álvarez in straight sets. At Wimbledon that year, she reached the singles quarterfinal, losing to world no. 1 and eventual champion Helen Wills in two sets. She missed the 1930 Wimbledon Championships due to a scheduling disagreement with the South African Lawn Tennis Union.
In the summer of 1938, she toured Europe for the third and final time, captaining the South African women team. In June, she lost the final of the Weybridge tournament in straight sets to Alice Marble. She won the singles and doubles titles at the Dutch Championships in July, defeating Nancye Wynne in the singles final in two sets. Heine did not participate in the French Championships and lost in the fourth round of singles at Wimbledon, again to Wills, in a closely fought two-set match. In doubles, she teamed up with countrywoman Margaret Morphew to reach the semifinal, where eventual champions Sarah Fabyan and Alice Marble prevailed in two sets.
Heine (Miller) won the South African Championships singles title on five occasions (1928, 1931, 1932, 1936 and 1937). Additionally, she won six doubles titles (1930, 1931, 1937, 1938, 1939 and 1947) and five mixed doubles titles (1930, 1936, 1937, 1938 and 1939). A final scheduled visit to Wimbledon in 1947 ended prematurely when her plane crashed in Egypt. All passengers survived and Heine Miller sustained only minor leg injuries, but her tennis gear was largely lost.