Adding additional controls above a ComboBox's ItemsPanel

I want to make a searchable ComboBox, with the search box being a TextBox that appears above the ItemsPanel when the ComboBox dropdown is expanded. I think I need to make a custom control to achieve the search functionality, but first I'm just trying to get the TextBox to show up using a normal ComboBox. Here's my current attempt, which is generating an exception when I try to expand the dropdown:

<Style x:Key="FilteredComboBox" TargetType="ComboBox">
    <Setter Property="ItemsPanel">
        <Setter.Value>
            <ItemsPanelTemplate>
                <StackPanel>
                    <TextBox/>
                    <StackPanel IsItemsHost="True"
                                Orientation="Horizontal"
                                VerticalAlignment="Center"
                                HorizontalAlignment="Center"/>
                    </StackPanel>

            </ItemsPanelTemplate>
        </Setter.Value>
    </Setter>
</Style>

The exception this is generating is:

Cannot explicitly modify Children collection of Panel used as ItemsPanel for ItemsControl. ItemsControl generates child elements for Panel.

I'm pretty sure there's a way to make this do what I want, but after several hours of googling and trial and error my head is now spinning. Any help would be greatly appreciated!

While the responses I got to this were all along the right track, I didn't think any of them really answered my question well enough to be marked as the solution. What I ended up doing was deriving a custom control from the ComboBox (right-click on a ComboBox in the designer and choose Edit Template -> Edit a Copy, this generates a whole bunch of XAML code for the ComboBox template which I copied into the Generic.xaml file of the custom control project I made). I then edited the Popup portion of the generated XAML code to add a WatermarkTextBox (from the Extended WPF Toolkit) above the ItemsPresenter like so:

<Popup x:Name="PART_Popup" AllowsTransparency="true" Grid.ColumnSpan="2" IsOpen="{Binding IsDropDownOpen, RelativeSource={RelativeSource TemplatedParent}}" Margin="1" PopupAnimation="{DynamicResource {x:Static SystemParameters.ComboBoxPopupAnimationKey}}" Placement="Bottom">
    <Themes:SystemDropShadowChrome x:Name="Shdw" Color="Transparent" MaxHeight="{TemplateBinding MaxDropDownHeight}" MinWidth="{Binding ActualWidth, ElementName=MainGrid}">
    <Border x:Name="DropDownBorder" BorderBrush="{DynamicResource {x:Static SystemColors.WindowFrameBrushKey}}" BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.WindowBrushKey}}">
        <ScrollViewer x:Name="DropDownScrollViewer">
        <Grid RenderOptions.ClearTypeHint="Enabled">
            <Canvas HorizontalAlignment="Left" Height="0" VerticalAlignment="Top" Width="0">
            <Rectangle x:Name="OpaqueRect" Fill="{Binding Background, ElementName=DropDownBorder}" Height="{Binding ActualHeight, ElementName=DropDownBorder}" Width="{Binding ActualWidth, ElementName=DropDownBorder}"/>
            </Canvas>
            <Grid>
            <Grid.RowDefinitions>
                <RowDefinition Height="Auto"/>
                <RowDefinition/>
            </Grid.RowDefinitions>
            <xtk:WatermarkTextBox Grid.Row="0"
                          Visibility="{Binding IsDropDownOpen, RelativeSource={RelativeSource TemplatedParent}, Converter={StaticResource booleanToVisibilityConverter}}"
                          Watermark="Type here to filter..."
                          Text="{Binding SearchFilter, RelativeSource={RelativeSource TemplatedParent}, UpdateSourceTrigger=PropertyChanged}">
            </xtk:WatermarkTextBox>
            <ItemsPresenter x:Name="ItemsPresenter" Grid.Row="1" KeyboardNavigation.DirectionalNavigation="Contained" SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}"/>
            </Grid>
        </Grid>
        </ScrollViewer>
    </Border>
    </Themes:SystemDropShadowChrome>
</Popup>

The SearchFilter property I'm binding the Text to is a property in my custom control's code-behind which then performs the actual filtering of the values in the ComboBox. It's a little beyond the scope of my original question but here's how I'm doing the filtering in case anyone is curious:

public class SearchableComboBox : ComboBox
{
    public const string SearchFilterPropertyName = "SearchFilter";
    public readonly static DependencyProperty SearchFilterProperty;
    public string SearchFilter
    {
        get { return (string)GetValue(SearchFilterProperty); }
        set { SetValue(SearchFilterProperty, value); }
    }

    static SearchableComboBox()
    {
        DefaultStyleKeyProperty.OverrideMetadata(typeof(SearchableComboBox), new FrameworkPropertyMetadata(typeof(SearchableComboBox)));

        SearchFilterProperty = DependencyProperty.Register(SearchFilterPropertyName, typeof(string), typeof(SearchableComboBox),
            new PropertyMetadata(string.Empty, new PropertyChangedCallback(SearchFilter_PropertyChanged)));

    }

    private static void SearchFilter_PropertyChanged(DependencyObject d, DependencyPropertyChangedEventArgs e)
    {
        ((SearchableComboBox)d).RefreshFilter();
    }

    private void RefreshFilter()
    {
        if (this.ItemsSource != null)
        {
            ICollectionView view = CollectionViewSource.GetDefaultView(this.ItemsSource);
            view.Refresh();
        }
    }

    private bool FilterPredicate(object value)
    {
        if (value == null)
            return false;

        if (string.IsNullOrEmpty(SearchFilter))
            return true;

        return value.ToString().Contains(SearchFilter, StringComparison.CurrentCultureIgnoreCase);
    }

    protected override void OnItemsSourceChanged(IEnumerable oldValue, IEnumerable newValue)
    {
        if (newValue != null)
        {
            ICollectionView view = CollectionViewSource.GetDefaultView(newValue);
            view.Filter += this.FilterPredicate;
        }

        if (oldValue != null)
        {
            ICollectionView view = CollectionViewSource.GetDefaultView(oldValue);
            view.Filter -= this.FilterPredicate;
        }

        base.OnItemsSourceChanged(oldValue, newValue);
    }