가능합니다. 안드로이드 매니페스트 파일에서 permission을 주고 <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />

<service android:name=".MyService" android:label="My Service">
    <intent-filter>
        <action android:name="com.myapp.MyService" />
    </intent-filter>
</service>

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

이런식으로 BOOT_COMPLETED를 받을수있게 리시버를 등록해줍니다.

public class StartMyServiceAtBootReceiver extends BroadcastReceiver {

    @Override
    public void onReceive(Context context, Intent intent) {
        if (Intent.ACTION_BOOT_COMPLETED.equals(intent.getAction())) {
            Intent serviceIntent = new Intent(context, MyService.class);
            context.startService(serviceIntent);
        }
    }
}

그리고 BOOT_COMPLETED를 받아서 처리하는 리시버 클래스를 정의해줍니다.