Can you save the parent entity in a one-to-many relationship in entity framework?

I have a simple, one-to-many, relationship between two entities.

public class Contact
{
    public string Id { get; set; }
    public string FirstName { get; set; }
    // the children
    public List<Message> Messages { get; set; }
}

public class Message
{
    public string Id { get; set; }
    public string ContactId { get; set; }
    public string Source { get; set; }
    // the parent
    public Contact Contact { get; set; }
}

Here's what the migration looks like

migrationBuilder.CreateTable(
                name: "Contact",
                columns: table => new
                {
                    Id = table.Column<string>(nullable: false),
                    FirstName = table.Column<string>(nullable: true)
                },
                constraints: table =>
                {
                    table.PrimaryKey("PK_Contact", x => x.Id);
                    table.UniqueConstraint("UK_Id", x => x.Id);
                });

            migrationBuilder.CreateTable(
                name: "Message",
                columns: table => new
                {
                    Id = table.Column<string>(nullable: false),
                    ContactId = table.Column<string>(nullable: true),                        
                    Source = table.Column<string>(nullable: true)
                },
                constraints: table =>
                {
                    table.PrimaryKey("PK_Message", x => x.Id);
                    table.UniqueConstraint("UK_Id", x => x.Id);
                    table.ForeignKey(
                        name: "FK_Message_Contact_ContactId",
                        column: x => x.ContactId,
                        principalTable: "Contact",
                        principalColumn: "Id");
                });

Now, I can create a new Contact, add a new Message to the Messages property, and save with no trouble. If I load that contact, I get all of the messages associated with it, no problem.

What I'm wondering is how to do this in reverse. I want to create a new message (that doesn't exist in the db yet), set the Contact property to a new contact object and save. I end up with a foreign key constraint (which makes sense. Can't save the message until the contact has been saved). But I thought entity framework was smart enough to figure out the relationships and know to insert the contact before the message. Am I configuring something wrong?

Update

Here's the unit test that I'm trying to pass

    [TestMethod]
    public void ShouldSaveEntityParentRelationshipsCorrectly()
    {
        var message = new Message
        {
            Id = "2848"
            , IsUrgent = true
            , MessageType = MessageType.Inbox
            , Note = "One ring to rule them all"
            , Contact = new Contact
            {
                Id = "454545"
                , FirstName = "Frodo"
                , LastName = "Baggins"
            }
        };

        service.Save(message); //Foreign key constraint error

        var entity = service.Find<Message>()
            .Include(c => c.Contact)
            .First(p => p.Id == "2848");

        Assert.AreEqual("Frodo", entity.Contact.FirstName);
        Assert.AreSame(entity, message, "Messages are not the same");

        Assert.IsNotNull(entity.Contact);

        Assert.AreSame(message.Contact, entity.Contact, "Contacts are not the same");
    }

Here's what service.Save does under the hood

public virtual void Save<T>(T entity) where T : class, IEntity
    {
        var context = Context();
        var entry = context.Entry(entity);
        var state = entry.State;

        if (state == EntityState.Detached)
            Add(entity);
        else if (state == EntityState.Deleted)
            Remove(entity);
        else
            Update(entity);

        SaveChanges();
    }

    public virtual void SaveChanges()
    {
        try
        {
            Context().SaveChanges();
        }
        catch (DbUpdateConcurrencyException ex)
        {
            Logger.Current.Log(ex);
            throw ex;
        }
    }

    public T Add<T>(T entity) where T : class, IEntity
    {
        return Context().Set<T>().Add(entity).Entity;
    }