Priority Queue in C#

I develop a small game using C# and need A* in it. For that, I need a PriorityQueue, which .NET does not have. I wanted to make my own one for practice. Here is it, please comment on performance and usability:

public class PriorityQueue<T> : IEnumerable
{
    List<T> items;
    List<int> priorities;

    public PriorityQueue()
    {
        items = new List<T>();
        priorities = new List<int>();
    }

    public IEnumerator GetEnumerator() { return items.GetEnumerator(); }
    public int Count { get { return items.Count; } }

    /// <returns>Index of new element</returns>
    public int Enqueue(T item, int priority)
    {
        for (int i = 0; i < priorities.Count; i++) //go through all elements...
        {
            if (priorities[i] > priority) //...as long as they have a lower priority.    low priority = low index
            {
                items.Insert(i, item);
                priorities.Insert(i, priority);
                return i;
            }
        }

        items.Add(item);
        priorities.Add(priority);
        return items.Count - 1;
    }

    public T Dequeue()
    {
        T item = items[0];
        priorities.RemoveAt(0);
        items.RemoveAt(0);
        return item;
    }

    public T Peek()
    {
        return items[0];
    }

    public int PeekPriority()
    {
        return priorities[0];
    }
}

I tested it with...

        PriorityQueue<String> pQ = new PriorityQueue<string>();

        for (int i = 0; i < 100; i++)
        {
            int prio = Provider.Rnd.Next(0, 1000);
            pQ.Enqueue(prio.ToString(), prio);
            if (pQ.Count > 0 && Provider.Rnd.Next(0, 2) == 0) pQ.Dequeue();
        }

        while (pQ.Count > 0)
        {
            Console.WriteLine(pQ.Dequeue());
        }