Solution 1:

Well here is a complete example of an AutoStart Application

AndroidManifest file

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="pack.saltriver" android:versionCode="1" android:versionName="1.0">

    <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />

    <application android:icon="@drawable/icon" android:label="@string/app_name">

        <receiver android:name=".autostart">
            <intent-filter>
                <action android:name="android.intent.action.BOOT_COMPLETED" />
            </intent-filter>
        </receiver>

        <activity android:name=".hello"></activity>
        <service android:enabled="true" android:name=".service" />
    </application>
</manifest>

autostart.java

public class autostart extends BroadcastReceiver 
{
    public void onReceive(Context context, Intent arg1) 
    {
        Intent intent = new Intent(context,service.class);
        if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.O) {
            context.startForegroundService(intent);
        } else {
            context.startService(intent);
        }
        Log.i("Autostart", "started");
    }
}

service.java

public class service extends Service
{
    private static final String TAG = "MyService";
    @Override
    public IBinder onBind(Intent intent) {
        return null;
    }
    public void onDestroy() {
        Toast.makeText(this, "My Service Stopped", Toast.LENGTH_LONG).show();
        Log.d(TAG, "onDestroy");
    }

    @Override
    public void onStart(Intent intent, int startid)
    {
        Intent intents = new Intent(getBaseContext(),hello.class);
        intents.setFlags(Intent.FLAG_ACTIVITY_NEW_TASK);
        startActivity(intents);
        Toast.makeText(this, "My Service Started", Toast.LENGTH_LONG).show();
        Log.d(TAG, "onStart");
    }
}

hello.java - This will pop-up everytime you start the device after executing the Applicaton once.

public class hello extends Activity 
{   
    public void onCreate(Bundle savedInstanceState) 
    {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.main);
        Toast.makeText(getBaseContext(), "Hello........", Toast.LENGTH_LONG).show();
    }
}

Solution 2:

Following should work. I have verified. May be your problem is somewhere else.

Receiver:

public class MyReceiver extends BroadcastReceiver{

    @Override
    public void onReceive(Context context, Intent intent) {
        if (Intent.ACTION_BOOT_COMPLETED.equals(arg1.getAction())) {
            Log.d("TAG", "MyReceiver");
            Intent serviceIntent = new Intent(context, Test1Service.class);
            context.startService(serviceIntent);
        }
    }
}

Service:

public class Test1Service extends Service {
    /** Called when the activity is first created. */
    @Override
    public void onCreate() {
        super.onCreate();
        Log.d("TAG", "Service created.");
    }
    
    @Override
    public int onStartCommand(Intent intent, int flags, int startId) {
        Log.d("TAG", "Service started.");
        return super.onStartCommand(intent, flags, startId);
    }
    
    @Override
    public void onStart(Intent intent, int startId) {
        super.onStart(intent, startId);
        Log.d("TAG", "Service started.");
    }
    @Override
    public IBinder onBind(Intent arg0) {
        return null;
    }
}

Manifest:

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
      package="com.test"
      android:versionCode="1"
      android:versionName="1.0"
      android:installLocation="internalOnly">
    <uses-sdk android:minSdkVersion="8" />

    <application android:icon="@drawable/icon" android:label="@string/app_name">
    
    <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />
    <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />
    <uses-permission android:name="android.permission.BATTERY_STATS" 
    />
<!--        <activity android:name=".MyActivity">
            <intent-filter>  
                <action android:name="android.intent.action.MAIN" /> 
                <category android:name="android.intent.category.LAUNCHER"></category> 
            </intent-filter>
       </activity> -->
        <service android:name=".Test1Service" 
                  android:label="@string/app_name"
                  >
        </service>
        <receiver android:name=".MyReceiver">  
            <intent-filter>  
                <action android:name="android.intent.action.BOOT_COMPLETED" /> 
            </intent-filter>  
        </receiver> 
    </application>
</manifest>

Solution 3:

Your Service may be getting shut down before it completes due to the device going to sleep after booting. You need to obtain a wake lock first. Luckily, the Support library gives us a class to do this:

public class SimpleWakefulReceiver extends WakefulBroadcastReceiver {
    @Override
    public void onReceive(Context context, Intent intent) {
        // This is the Intent to deliver to our service.
        Intent service = new Intent(context, SimpleWakefulService.class);

        // Start the service, keeping the device awake while it is launching.
        Log.i("SimpleWakefulReceiver", "Starting service @ " + SystemClock.elapsedRealtime());
        startWakefulService(context, service);
    }
}

then, in your Service, make sure to release the wake lock:

    @Override
    protected void onHandleIntent(Intent intent) {
        // At this point SimpleWakefulReceiver is still holding a wake lock
        // for us.  We can do whatever we need to here and then tell it that
        // it can release the wakelock.

...
        Log.i("SimpleWakefulReceiver", "Completed service @ " + SystemClock.elapsedRealtime());
        SimpleWakefulReceiver.completeWakefulIntent(intent);
    }

Don't forget to add the WAKE_LOCK permission:

<uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />
<uses-permission android:name="android.permission.WAKE_LOCK" />