A painting once thought to depict Catherine but now thought to depict a member of the Cromwell family.

Catherine's exact birth date and year is unknown, however it is generally agreed she was born in 1522 or 1523. After her mother passed away when she was a child, she was sent to live with her grandmother, the Dowager Duchess of Norfolk. Catherine was not the only young girl living with the dowager duchess. It was common at the time for children of aristocrats to be sent to live with upstanding nobles to be trained properly in etiquette and educated according to the standards of the time.

Around 1536 when Catherine was likely 13 or 14, she began music lessons taught by a man named Henry Mannox. Catherine and Mannox began a relationship, one that was inappropriate mainly because of their difference in class. The age of Mannox is unknown, and theories have been put forth that he could have been as old as 36, however there is no evidence to support this. Based on the average ages of his friend group, he likely wouldn't have been more than 5 years older than Catherine, at most. During the music lessons, Catherine was chaperoned, which meant that their relationship progressed slowly and began through sending mutual gifts to each other with the help of one of the house's maids. They did eventually find moments to steal away together, and were caught by the dowager duchess on more than one occassion, after which Catherine was slapped as punishment.

As would later come out during the questioning of both Mannox and Catherine during Catherine's trial, the two engaged in foreplay but did not have sex. This led to a comment made by him to Mary Lascelles, a nursemaid in the Howard household, who tried to warn Mannox that he should stop pursuing a relationship with Catherine because of their class difference. Angered, Mannox told her "I have had her by the cunt and she hath said to me that I shall have her maidenhead though it be painful to her, not doubting but I will be good to her hereafter." The comment was spread through the household by gossip and soon reached Catherine's ears, who angrily broke off the relationship.

In 1538, Catherine began a relationship with Francis Dereham, her grandmother's secretary. The two would rendezvous in Catherine's bed chambers, which were more like a dormitory as all the young ladies of the household slept there. To make this easier, Catherine stole the key to the room and had a copy made so she could unlock the door during the night. Many of the girls Catherine lived with had lovers who would visit them in their rooms, so this made it easier for multiple rendezvous to be held.

Unlike with Mannox, Catherine and Dereham engaged in sex mere months into their relationship. This was not only confirmed by Catherine and Dereham during questioning, but also by the girls who she shared her room with, one of whom, Alice Wilkes, she shared a bed with and who had multiple unpleasant nights where the couple engaged in relations right next to her. This would pose a problem to Catherine during her trial, as she had claimed to be a virgin when she married Henry. Dereham and Catherine were so in love that they referred to each other as husband and wife. Just as before with Mannox, the dowager duchess did catch the two of them at one time, and this time retaliated by punching the couple and launching into a tirade. Even still, Dereham was allowed to keep his job and the relationship continued.

Despite the lovey doveyness of the beginning of their relationship, Catherine eventually grew tired of Dereham. Dereham wished to get married and proposed the idea to Catherine on multiple occasions, but Catherine was evasive. When Catherine was presented with an opportunity to leave and join the Tudor court as a member of the queen's household, she leapt at the chance and broke things off with Dereham.