Detect is when a windows service has been deleted

While there is no trace of service deletion in Event or Audit logs, what you can do is create a small console app that detects if a service exists and attach this app to Windows Task Scheduler such that it is scheduled to execute based on frequency or a Trigger that you can customize to your requirements such that you will receive an alert if a service has been added or removed etc..

The console app is designed such that on the first run, it logs all the services on the system and on the subsequent runs it will be tracking changes made on the services via servicesRemoved and servicesAdded, with this we can decide what action to take when a service has been modified

Console App: ServiceDetector.exe

static void Main(string[] args)
{
    var path = @"C:\AdminLocation\ServicesLog.txt";

    var currentServiceCollection = ServiceController.GetServices().Select(s => s.ServiceName).ToList(); //Queries the most current Services from the machine

    if (!File.Exists(path)) //Creates a Log file with current services if not present, usually means the first run
    {
        // Assumption made is that this is the first run
        using (var text = File.AppendText(path))
        {
            currentServiceCollection.ForEach((s) => text.WriteLine(s));
        }
        return;
    }

    // Fetches the recorded services from the Log
    var existingServiceCollection = File.ReadAllLines(path).ToList();

    var servicesRemoved = existingServiceCollection.Except(currentServiceCollection).ToList();
    var servicesAdded = currentServiceCollection.Except(existingServiceCollection).ToList();

    if (!servicesAdded.Any() && !servicesRemoved.Any())
    { Console.WriteLine("No services have been added or removed"); return; }

    //If any services has been added
    if (servicesAdded.Any())
    {
        Console.WriteLine("One or more services has been added");
        using (var text = File.AppendText(path))
        {
            servicesAdded.ForEach((s) => text.WriteLine(s));
        }
        return;
    }
    //Service(s) may have been deleted, you can choose to record it or not based on your requirements
    Console.WriteLine("One or more services has been removed");

}

Scheduling Task

Windows Start > Task Scheduler > Create Basic Task > Set Trigger > Attach your exe > Finish