Typically when you create a relationship class, you would add both tables/features to the map for publishing. I've done this on multiple occasions.
I don't know how your relationship is set up, but depending on how it is setup, you will need to add all of the tables/features that participate in that relationship(s).
For instance, I have a sample where I have multiple features relating to a single standalone table.
- All of the features plus the standalone table are brought into a single map.
- From the standalone map, I publish everything as is (the relationship will still be honored despite the user not seeing it).
So doing this should give you what you need.