Learning to create your own vocal harmony part along with a melody is often something that musicians learn intuitively, through listening to a lot of music, but also by singing in a band or choir. Having said this, there is nothing wrong with taking a short cut towards gaining this skill, by using a little musical knowledge. You can create vocal (or any other, for that matter) harmony parts, using some basic knowledge of harmony (certainly not as advanced as harmonising chorales in the style of Bach, but a good deal above the level of simply trying to find what "sounds good" with a trial-and-error approach).
Below is a very simple melody; following it are a series of steps designed to create a reasonably interesting harmony to go with it. Following these steps will help you to connect more closely with the harmony, and separate yourself from the main melody.
Importantly, the underlying chords (the harmony), are also shown; the melody and any harmony parts need to predominately use notes from these chords, unless you are specifically trying to have your melody or harmony parts reacting "against" the harmony (dissonant), which is quite a bit more advanced.
So, the first chord "C" has the notes C, E and G; the second chord "F" has F, A and C; the third chord "G" has G, B and D. The easiest approach to harmonisation is to simply have the harmony part follow the underlying chords, and the easiest way to do this is to just follow the root notes C, F, G:
Okay, this will work, but it is pretty dull, especially as the harmony and melody parts mostly have the same notes. Instead of using these root notes, we could use other chord tones:
Right, this is starting to sound far more interesting, now let's make the harmony part match the melody part by using: chord tones when the melody has chord tones; non-chord tones when the melody has non-chord tones:
This results in the classic "harmonisation-in-thirds". What if we want the harmony part to sound a little more distinct from the melody? Well, we could use different chord tones to start with, let's try having the harmony part move in contrary motion (opposite direction) to the melody:
Nice! (Even if I do say so myself…) Now we could finish off by putting non-chord tones into the harmony part:
This is just a very simple example of course, and as I say a lot of this becomes intuitive as you sing, play and listen to more music. I am also aware that you may need to read up on some of the terms here (chord tones, non-chord tones etc.) I'll put some links in...